package study;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CountSmaller {
    private int[] index;
    private int[] helper;
    private int[] count;

    // 依葫芦画瓢学习，但还没搞懂
    public int[] countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>(nums.length);
        index = new int[nums.length];
        helper = new int[nums.length];
        count = new int[nums.length];
        for (int i = 0; i < index.length; i++) {
            index[i] = i;
        }
        merge(nums, 0, nums.length - 1);
        for (int i = 0; i < count.length; i++) {
            res.add(i, count[i]);
        }
        int[] ret = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ret[i] = res.get(i);
        }
        return ret;
    }

    private void merge(int[] nums, int left, int right) {
        if (left == right || left > right) return;
        int mid = (left + right) >> 1;
        if (left < mid) {
            merge(nums, left, mid);
        }

        if (mid + 1 < right) {
            merge(nums, mid + 1, right);
        }
        int i = left, j = mid + 1;
        int hi = left;
        while (i <= mid && j <= right) {
            if (nums[index[i]] <= nums[index[j]]) {
                helper[hi++] = index[j++];
            } else {
                count[index[i]] += right - j + 1;
                helper[hi++] = index[i++];
            }
        }
        while (i <= mid) {
            helper[hi++] = index[i++];
        }
        while (j <= right) {
            helper[hi++] = index[j++];
        }
        for (int k = left; k <= right; k++) {
            index[k] = helper[k];
        }
    }

    // 对拍
    public int[] countSmaller2(int[] nums) {
        int[] ret = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    ret[i]++;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        CountSmaller countSmallerObject = new CountSmaller();
        int[] num1 = {5, 2, 6, 1};
        int[] ret = countSmallerObject.countSmaller(num1);
        int[] ret2 = countSmallerObject.countSmaller2(num1);
        System.out.println(Arrays.toString(ret));
        System.out.println(Arrays.toString(ret2));
    }
}
